package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class _145_post_order {
    
    /**
     * 树后序遍历迭代方法是很难的
     * 自己想基本不可能想出来除非你是个高手
     *
     * 陈词滥调，后序遍历
     * 但是这个迭代法，很能锻炼你的思维
     *
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        LinkedList<TreeNode> stack = new LinkedList<>();
        
        
        // 这个变量极其重要，值得单独放到一行，并且上下各空出来两行以表尊敬
        // 这个 prev，是真实的 prev，是上一个被记录的节点
        // 后序不是 左 - 右 - 根 吗，右会紧挨着根，
        // 所以，如果上一个访问的是根的右孩子，说明现在可以访问根了
        TreeNode prev = null;
        
        
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.peek();
            // 到头之后，如果有右孩子，没访问过，是不能访问根节点的！
            if (node.right != null && node.right != prev) {
                root = node.right;
            }
            // 没有右孩子或右孩子访问过，该访问 root 了
            else {
                stack.pop();
                res.add(node.val);
                // 如果右边还有节点，后面会判断 prev 是不是当前节点的右孩子，会返回 true
                prev = node;
                root = null;
            }
        }
        return res;
    }
    
    /**
     * morris 遍历看一次忘一次
     * 这次不看了，下次一定
     * */
    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode rightMostChild = cur.left;
                while (rightMostChild.right != null && rightMostChild.right != cur) {
                    rightMostChild = rightMostChild.right;
                }
                if (rightMostChild.right == null) {
                    rightMostChild.right = cur;
                    cur = cur.left;
                    continue;
                }
                else {
                    rightMostChild.right = null;
                    reversedAppend(res, cur.left);
                }
            }
            cur = cur.right;
        }
        reversedAppend(res, root);
        return res;
    }
    
    private void reversedAppend(List<Integer> res, TreeNode node) {
        int count = 0;
        while (node != null) {
            res.add(node.val);
            node = node.right;
            count++;
        }
        int left = res.size() - count, right = res.size() - 1;
        while (left < right) {
            int t = res.get(left);
            res.set(left, res.get(right));
            res.set(right, t);
            left++; right--;
        }
    }
}
